package leetcode;

import java.util.PriorityQueue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-21 23:25
 **/
public class LeetCode2182 {

    public String repeatLimitedString(String s, int repeatLimit) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int[] letters = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            ++letters[c - 'a'];
        }

        for (int i = 0; i < letters.length; i++) {
            if (letters[i] != 0) {
                pq.offer(new int[]{i + 'a', letters[i]});
            }
        }

        StringBuilder ans = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] poll = pq.poll();
            int cnt = poll[1];
            char c = (char) poll[0];
            for (int i = 0; i < Math.min(repeatLimit, poll[1]); i++) {
                ans.append(c);
                --cnt;
            }

            if (cnt > 0) {
                if (pq.isEmpty()) {
                    return ans.toString();
                }

                int[] poll2 = pq.poll();
                int cnt2 = poll2[1];
                char c2 = (char) poll2[0];
                ans.append(c2);
                --cnt2;

                if (cnt2 > 0) {
                    poll2[1] = cnt2;
                    pq.add(poll2);
                }

                poll[1] = cnt;
                pq.add(poll);
            }

        }
        return ans.toString();
    }

}
